package com.lfg.leetcode.leetcode0;

public class No84largestRectangleArea {

    public static void main(String[] args) {
        int ret = largestRectangleArea(new int[]{15, 6, 8, 1, 2, 3, 1, 0, 11});
        System.out.println(ret);
    }

    public static int largestRectangleArea(int[] heights) {
        return findMaxArea(heights, 0, heights.length - 1);
    }

    public static int findMaxArea(int[] heights, int i, int j) {
        if (i > j) {
            return 0;
        }
        int ret = heights[i];
        int minIndex = i;
        boolean isSorted = true;
        for (int n = i + 1; n <= j; n++) {
            if (isSorted && heights[n - 1] > heights[n]) {
                isSorted = false;
            }
            if (heights[minIndex] > heights[n]) {
                minIndex = n;
            }
        }
        if (isSorted) {
            for (int n = i; n <= j; n++) {
                ret = Math.max(ret, heights[n] * (j - n + 1));
            }
            return ret;
        }
        int left = findMaxArea(heights, i, minIndex - 1);
        int right = findMaxArea(heights, minIndex + 1, j);
        ret = Math.max(ret, heights[minIndex] * (j - i + 1));
        ret = Math.max(left, ret);
        ret = Math.max(right, ret);
        return ret;
    }

    public static int largestRectangleArea2(int[] heights) {
        int ret = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = heights[i];
            ret = Math.max(ret, minHeight);
            for (int j = i + 1; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                ret = Math.max(ret, (j - i + 1) * minHeight);
            }
        }
        return ret;
    }

}

